' \ufeffPlease solve the following recurrences using substitution…

Question

Anu Bhardwaj · Accepted Answer

Assume a solution form : Let's assume 𝑇 ( 𝑛 ) = 𝑂 ( 𝑛 log ⁡ 𝑛 ) T ( n ) = O ( n lo g n ) . Substitute the assumption : 𝑇 ( 𝑛 ) = 3 𝑇 ( 𝑛 3 ) + 𝑛 2 T ( n ) = 3 T ( 3 n ​ ) + 2 n ​ Assume 𝑇 ( 𝑛 ) = 𝑐 ⋅ 𝑛 log ⁡ 𝑛 T ( n ) = c ⋅ n lo g n for some constant 𝑐 c : 𝑇 ( 𝑛 ) = 3 ( 𝑐 ⋅ 𝑛 3 log ⁡ ( 𝑛 3 ) ) + 𝑛 2 T ( n ) = 3 ( c ⋅ 3 n ​ lo g ( 3 n ​ ) ) + 2 n ​ Simplify the logarithmic term: 𝑇 ( 𝑛 ) = 3 ( 𝑐 ⋅ 𝑛 3 ( log ⁡ 𝑛 − log ⁡ 3 ) ) + 𝑛 2 T ( n ) = 3 ( c ⋅ 3 n ​ ( lo g n − lo g 3 ) ) + 2 n ​ 𝑇 ( 𝑛 ) = 3 ( 𝑐 ⋅ 𝑛 3 log ⁡ 𝑛 − 𝑐 ⋅ 𝑛 3 log ⁡ 3 ) + 𝑛 2 T ( n ) = 3 ( c ⋅ 3 n ​ lo g n − c ⋅ 3 n ​ lo g 3 ) + 2 n ​ 𝑇 ( 𝑛 ) = 𝑐 ⋅ 𝑛 log ⁡ 𝑛 − 𝑐 ⋅ 𝑛 log ⁡ 3 + 𝑛 2 T ( n ) = c ⋅ n lo g n − c ⋅ n lo g 3 + 2 n ​ Group the terms: 𝑇 ( 𝑛 ) = 𝑐 ⋅ 𝑛 log ⁡ 𝑛 − 𝑐 ⋅ 𝑛 log ⁡ 3 + 𝑛 2 T ( n ) = c ⋅ n lo g n − c ⋅ n lo g 3 + 2 n ​ Find the constant : For 𝑇 ( 𝑛 ) T ( n ) to be 𝑂 ( 𝑛 log ⁡ 𝑛 ) O ( n lo g n ) , the lower-order terms should be dominated by the 𝑐 ⋅ 𝑛 log ⁡ 𝑛 c ⋅ n lo g n term: 𝑇 ( 𝑛 ) = 𝑐 ⋅ 𝑛 log ⁡ 𝑛 − 𝑐 ⋅ 𝑛 log ⁡ 3 + 𝑛 2 ≈ 𝑐 ⋅ 𝑛 log ⁡ 𝑛 T ( n ) = c ⋅ n lo g n − c ⋅ n lo g 3 + 2 n ​ ≈ c ⋅ n lo g n Hence, the solution is: 𝑇 ( 𝑛 ) = 𝑂 ( 𝑛 log ⁡ 𝑛 ) T ( n ) = O ( n lo g n ) Master Theorem The given recurrence relation 𝑇 ( 𝑛 ) = 3 𝑇 ( 𝑛 / 3 ) + 𝑛 2 T ( n ) = 3 T ( n /3 ) + 2 n ​ can be compared to the general form: 𝑇 ( 𝑛 ) = 𝑎 𝑇 ( 𝑛 𝑏 ) + 𝑓 ( 𝑛 ) T ( n ) = a T ( b n ​ ) + f ( n ) Here, 𝑎 = 3 a = 3 , 𝑏 = 3 b = 3 , and 𝑓 ( 𝑛 ) = 𝑛 2 f ( n ) = 2 n ​ . Compute log ⁡ 𝑏 𝑎 lo g b ​ a : log ⁡ 3 3 = 1 lo g 3 ​ 3 = 1 Compare 𝑓 ( 𝑛 ) f ( n ) with 𝑛 log ⁡ 𝑏 𝑎 n l o g b ​ a : 𝑓 ( 𝑛 ) = 𝑛 2 = 𝑂 ( 𝑛 ) f ( n ) = 2 n ​ = O ( n ) 𝑛 log ⁡ 𝑏 𝑎 = 𝑛 1 = 𝑛 n l o g b ​ a = n 1 = n We see that 𝑓 ( 𝑛 ) = 𝑂 ( 𝑛 log ⁡ 𝑏 𝑎 ⋅ log ⁡ 𝑘 𝑛 ) f ( n ) = O ( n l o g b ​ a ⋅ lo g k n ) with 𝑘 = 0 k = 0 . Apply Master Theorem (Case 2): If 𝑓 ( 𝑛 ) = Θ ( 𝑛 log ⁡ 𝑏 𝑎 log ⁡ 𝑘 𝑛 ) f ( n ) = Θ ( n l o g b ​ a lo g k n ) for 𝑘 = 0 k = 0 , then: 𝑇 ( 𝑛 ) = Θ ( 𝑛 log ⁡ 𝑏 𝑎 log ⁡ 𝑘 + 1 𝑛 ) T ( n ) = Θ ( n l o g b ​ a lo g k + 1 n ) 𝑇 ( 𝑛 ) = Θ ( 𝑛 log ⁡ 𝑛 ) T ( n ) = Θ ( n lo g n ) Final Answer:- Both the substitution method and the Master Theorem confirm that the solution to the recurrence relation 𝑇 ( 𝑛 ) = 3 𝑇 ( 𝑛 / 3 ) + 𝑛 2 T ( n ) = 3 T ( n /3 ) + 2 n ​ is: 𝑇 ( 𝑛 ) = Θ ( 𝑛 log ⁡ 𝑛 ) T ( n ) = Θ ( n lo g n )

AI tools

Study help

Free tools

Earn & more

Computer science

Computer science

Anu Bhardwaj

Answer

Extracted Transcript from Images

AI

Study help

Earn & more

Company